package com.cskaoyan.com.stack;

/**
 * 使用单向链表实现一个数据结构为栈的数据容器/集合类
 */
public class MyLinkedStack <T> {
    private Node head; // 底层链表的头结点, 还是栈的栈顶
    private int size; // MyLinkedStack中存储的数据量


    // 添加(入栈), 出栈(删除),  查找(查看栈顶数据)
    // 添加/入栈:  push
    // 删除/出栈:  pop
    // 查看栈顶元素: peek

    /**
     * 栈的入栈操作
     * @param value: 要入栈的内容
     * @return: 入栈是否成功
     */
    public boolean push(T value){

        Node node = new Node(value);
        node.next = head;
        head = node;

        // head = new Node(value, head);
        size++;

        return true;
    }

    /**
     * 栈的出栈操作
     * @return: 原栈顶的数据
     */
    public T pop(){
        if (isEmpty()){
            // 栈为空
            // 返回null  , 或者抛出异常
            throw new RuntimeException("stack is empty");
        }

        // 栈不空

        // 保存旧值
        T oldValue = head.value;
        // 头标记后移
        head = head.next;

        size--;

        return oldValue;
    }

    /**
     * 栈的查看栈顶元素的方法
     * @return: 栈顶元素
     */
    public T peek(){
        if (isEmpty()){
            // 栈为空
            // 返回null  , 或者抛出异常
            throw new RuntimeException("stack is empty");
        }

        return head.value;
    }


    public boolean isEmpty(){
        return size == 0;
    }

    // 单向链表的结点
    class Node{
        T value; //值域
        Node next; // 指针域
        public Node(T value) {
            this.value = value;
        }
        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
